class LFUCache:

    def __init__(self, capacity: int):
        self.map = dict()
        self.counter = dict()
        self.cap = capacity
        self.size = 0

    def get(self, key: int) -> int:
        if self.size == 0:
            return -1
        if key in self.map:
            [value, count] = self.map[key]
            self.incrKeyUsedCount(key, count)
            self.map[key][1] = count + 1
            return value
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            [_, count] = self.map[key]
            self.map[key][0] = value
            self.map[key][1] = count + 1
            self.incrKeyUsedCount(key, count)
            return

        if self.size < self.cap:
            self.map[key] = [value, 1]
            self.addCount(key, 1)
            self.size += 1
        else:
            self.removeLastKey()
            self.size -= 1
            self.put(key, value)

    def addCount(self, key: int, count: int) -> None:
        if count in self.counter:
            self.counter[count] = [key, *self.counter[count]]
        else:
            self.counter[count] = [key]

    def removeLastKey(self) -> None:
        if self.size == 0:
            return

        leastUsedCount = sorted(self.counter.keys())[0]
        [*latest, last] = self.counter[leastUsedCount]
        self.map.pop(last)

        self.counter[leastUsedCount] = latest
        if len(latest) == 0:
            self.counter.pop(leastUsedCount)

    def incrKeyUsedCount(self, key: int, count: int) -> None:
        self.counter[count].remove(key)
        if len(self.counter[count]) == 0:
            self.counter.pop(count)

        self.addCount(key, count + 1)


cache = LFUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))   # 返回 1
cache.put(3, 3)      # 去除 key 2
print(cache.get(2))   # 返回 -1 (未找到key 2)
print(cache.get(3))   # 返回 3
cache.put(4, 4)      # 去除 key 1
print(cache.get(1))   # 返回 -1 (未找到 key 1)
print(cache.get(3))   # 返回 3
print(cache.get(4))   # 返回 4


c2 = LFUCache(2)
c2.put(3, 1)
c2.put(2, 1)
c2.put(2, 2)
c2.put(4, 4)
print(c2.get(2))  # 返回 2

c3 = LFUCache(2)
c3.put(2, 1)
c3.put(1, 1)
c3.put(2, 3)
c3.put(4, 1)
print(c3.get(1))  # -1
print(c3.get(2))  # 3
